package sjjg.graph;

import java.util.Stack;

public class DepthFirstOrder {//顶点搜索
    private boolean[]marked;
    private Stack<Integer>reversePost;//用来存储排序后的节点
    DepthFirstOrder(Digraph digraph){
          if(digraph==null){
              return;
          }
          marked=new boolean[digraph.V()];
          reversePost=new Stack<>();
          //保证对每个节点都进行一次深度优先搜索
        for (int v = 0; v < digraph.V(); v++) {
             //如果被深度搜索过就没必要再搜索了
            if (!marked[v]) {
                dfo(digraph,v);
            }
        }
    }
    private void dfo(Digraph digraph,int v){
            marked[v]=true;
        for (Integer w : digraph.adj(v)) {
             if(!marked[w]){
                 dfo(digraph,w);
             }
        }
        reversePost.push(v);//搜索完一个节点后就入栈 最后让这些元素出栈就得到了一个图的线性排序(拓扑排序)
    }
    public Stack<Integer>reversePost(){
        return reversePost;
    }
}
